1 二叉查找树（Binary Search Tree）

二叉查找树要求，在树中的任意一个节点，其左子树 中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值

image-20191010095731619

上面我们是手动创建二叉树的，一般地：都是给出一个数组给你，让你将数组变成一个二叉树，此时就需要我们动态创建二叉树了。

二叉树中还有一种特殊的二叉树：二叉查找树(binary search tree)

  • 定义：

    #########当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大

  • 明眼人可以看出，这对我们来找一个数是非常方便快捷的

往往我们动态创建二叉树都是创建二叉查找树

#2 构建二叉树

2.1动态创建二叉树体验

假设我们有一个数组：int[] arrays = {3, 2, 1, 4, 5};

那么创建二叉树的步骤是这样的：

  • 首先将3作为根节点

img

  • 随后2进来了，我们跟3做比较，比3小，那么放在3的左边

img

  • 随后1进来了，我们跟3做比较，比3小，那么放在3的左边，此时3的左边有2了，因此跟2比，比2小，放在2的左边

img

  • 随后4进来了，我们跟3做比较，比3大，那么放在3的右边

img

  • 随后5进来了，我们跟3做比较，比3大，那么放在3的右边，此时3的右边有4了，因此跟4比，比4大，放在4的右边

img

那么我们的二叉查找树就建立成功了，无论任何一颗子树，左边都比根要小，右边比根要大

img

3 二分搜索树定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//BST 二分搜索树
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根结点
    private Node root;//根结点
    private int size;//记录存储了多少个元素

    public BST() {
        root = null;
        size = 0;
    }
  }

4 二分搜索树添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//BST 二分搜索树
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根结点
    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    //向二分搜索树中添加新的元素
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            add(root, e);//从根结点开始插入元素e
        }
    }

    //向以node为根的二分搜索树中插入元素E 递归算法
    private void add(Node node, E e) {
        //1  递归终止条件
        if (e.equals(node.e)) {
            return;
        } else if (e.compareTo(node.e) < 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (e.compareTo(node.e) > 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        }
        // 2 调用递归函数
        if (e.compareTo(node.e) < 0) {
            add(node.left, e);
        } else
            add(node.right, e);
    }
}

5 二叉查找树的查找操作

首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找 的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要 查找的数据比根节点的值大，那就在右子树中递归查找。

image-20191010105102809

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class BinarySearchTree {

    private Node tree;

    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) {
                p = p.left;
            } else if (data > p.data) {
                p = p.right;
            } else return p;
        }
        return null;
    }

    public static class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }

6 二叉查找树的插入操作

二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上，所以我们 只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点 的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节 点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再 递归遍历左子树，查找插入位置

image-20191010105738553